package com.acwing.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:归并排序 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性 稳定
 * User:yxd
 * Date:2022-01-11
 * Time:0:31
 */
import java.util.*;
public class Merge{
    static int N = 100005;
    static int[] q = new int[N];//结果数组
    static int[] p = new int[N];//排序数组
    static int n;
    //归并排序模板
    public static void merge_sort(int l,int r){
        if(l >= r)return;
        int mid = (l + r) / 2;//从中间节点分界

        merge_sort(l,mid); merge_sort(mid + 1,r);//递归排序前后两串数字
        int k = 0,i = l,j = mid + 1;//定义已排好序的两个数列头 k代表要排新数组的个数
        while(i <= mid && j <= r){
            if(q[i] < q[j]) {//将两数列中 较小的值 放在新数组里  如果相同默认放第一个数列的到新数组
                p[k++] = q[i++];
            } else {
                p[k++] = q[j++];

            }
        }//此时已经将某一数列完成了 现在只需将剩下的数列排在新数组的后面即可
        while(i <= mid){//
            p[k++] = q[i++];
        }
        while(j <= r){
            p[k++] = q[j++];
        }
        for(i = l,j = 0;i <= r;i++,j++){
            q[i] = p[j]; //将排好序的新数组  再放回到原数组
        }


    }
    public static void main1(String[] args){
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        for(int i = 0;i < n;i ++){
            q[i] = input.nextInt();
        }
        merge_sort(0,n - 1);
        for(int i = 0;i < n;i ++){
            System.out.print(q[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] a = {15,24,1,47,2,15,24};
        mergeSort1(a);
        System.out.println(Arrays.toString(a));
    }
    public static void mergrSort(int[] array){
        mergeSortInternal(array,0, array.length - 1);
    }
    private static void mergeSortInternal(int[] array, int left, int right) {
        if(left >= right)return;//递归结束条件
        int mid = left + (right - left) / 2;
        mergeSortInternal(array,left,mid);//左边
        mergeSortInternal(array,mid + 1,right);//右边
        merge(array,left,mid,right);//合并
    }
    private static void merge(int[] array,int left,int mid,int right){
        int[] tmp = new int[right - left + 1];//合并两个有序数组
        int k = 0;
        int s1 = left;
        int s2 = mid + 1;
        while(s1 <= mid && s2 <= right){
            if(array[s1] <= array[s2]){//没有等于就是不稳定的，没有等号就是稳定的排序
                tmp[k ++] = array[s1 ++];
            }else{
                tmp[k ++] = array[s2++];
            }
        }
        while(s1 <= mid){
            tmp[k ++] = array[s1 ++];
        }
        while(s2 <= right){
            tmp[k ++] = array[s2 ++];
        }
        for (int i = 0; i < k; i++) {
            array[i + left] = tmp[i];//把合并的数再次赋值给原数组
        }
    }
    //非递归的归并排序
    public static void mergeSort1(int[] array){
        int nums = 1;//每组数的个数
        while(nums < array.length){
            for (int i = 0; i < array.length; i += 2 * nums) {
                int left = i;
                int mid = left + nums - 1;
                if(mid >= array.length){
                    mid = array.length - 1;
                }
                int right = mid + nums;
                if(right >= array.length){
                    right = array.length - 1;
                }
                //下标确定再进行合并
                merge(array,left,mid,right);
            }
            nums *= 2;

        }
    }
}
